package uk.org.landeg.euler.problems;

import java.util.ArrayList;

import uk.org.landeg.euler.PrimeGen;
import uk.org.landeg.euler.problems.framework.AbstractProblem;
import uk.org.landeg.euler.problems.framework.ProblemLauncher;

public class Problem070 extends AbstractProblem {

	public static void main(String[] args) {
		ProblemLauncher launcher = new ProblemLauncher(new Problem070());
		launcher.solve();
	}

	@Override
	public String getDescription() {
		return "Investigate values of n for which φ(n) is a permutation of n.";
	}

	@Override
	public Integer getProblemNumber() {
		// TODO Auto-generated method stub
		return 70;
	}

	@Override
	public Object solve() {
		PrimeGen.generate((long)(1e6));
		ArrayList<Long> primes = new ArrayList<Long> ();
		primes.addAll(PrimeGen.getPrimes());
		System.out.println(primes.size());
		System.out.println(PrimeGen.factorise(87109));
		int i1,i2,h = primes.size() / 2;
		i1 = primes.size()-1;
		long p1,p2;
		long phi,n;
		long max = (long)Math.sqrt(100000000);
		double ratio,rMax=2;
		for (i1 = 0 ; i1 < primes.size() ; i1++) {
			p1 = primes.get(i1);
			for (i2 = i1 + 1 ; i2 < primes.size() ; i2++) {
				p2 = primes.get(i2);
				if (p2 > max) {
					break;
				}
				n = p2 * p1;
				if (n > 10000000) {
					break;
				}
				phi = (p2-1) * (p1-1);
				if (PrimeGen.isPermutation(phi, n)) {
					ratio = (double)n/(double)phi;
					if (ratio < rMax) {
						System.out.println(p1 + "," + p2 + "\t" + n + "\t" + phi + "\t" + ratio);
						rMax = ratio;
					}
				}
			}
		}
		return rMax;
	}


}
